1073G - Yet Another LCP Problem - CodeForces Solution

#include <bits/stdc++.h>
//#define int __int128
#define int long long

using namespace std;
const int N=4e5+5;
void chkmax(int &x,int y){x=max(x,y);}
void chkmin(int &x,int y){x=min(x,y);}
void Add(int &x,int y){x+=y;}
int ab(int x){if(x<0)x=-x;return x;}

int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=getchar();
	return x*f;
}
struct str{
	int sum[N],rk[N],sa[N],lrk[N*2],height[N],id[N],n;
	int st[N][20];
	char s[N];
	void clear(){
		for(int i=1;i<=2*n;i++)lrk[i]=0,s[i]=' ';
	}
	int cmp(int x,int y,int k){
		return (lrk[x]==lrk[y])&&(lrk[x+k]==lrk[y+k]);
	}
	int query(int l,int r){
		int k=log2((long long)(r-l+1));
		return min(st[l][k],st[r-(1<<k)+1][k]);
	} 
	int lcp(int x,int y){
		if(x==y)return n-x+1;
		int l=rk[x],r=rk[y];
	  if(l>r)swap(l,r);
	  return query(l+1,r);
	}
	int b[N],stl[N],str[N],dst[N],a2[N];
	int get_ans(int *a,int k){
		int ans=0,nk=0;
		sort(a+1,a+k+1,[&](int x,int y){return rk[x]<rk[y];});
		for(int i=1;i<=k-1;i++)b[i]=lcp(a[i],a[i+1]);
//		for(int i=1;i<=k;i++)printf("%lld ",b[i]);
//		printf("\n");
		for(int i=1,r=0;i<=k-1;i++){
			while(r&&b[dst[r]]>b[i])r--;
			stl[i]=dst[r];dst[++r]=i;
		}
		for(int i=k-1,r=0;i>=1;i--){
			while(r&&b[dst[r]]>=b[i])r--;
			str[i]=dst[r];dst[++r]=i;if(!str[i])str[i]=k; 
		}
//		for(int i=1;i<=k-1;i++)printf("%lld %lld %lld\n",i,stl[i],str[i]);
		for(int i=1;i<=k-1;i++){
			ans+=b[i]*(i-stl[i])*(str[i]-i);
		}
		return ans;
	} 
	void build_height(){
		int k=0;
		for(int i=1;i<=n;i++){
			if(k)k--;
			while(s[i+k]==s[sa[rk[i]-1]+k])k++;
			height[rk[i]]=k;
		}
//		printf("height->");for(int i=1;i<=n;i++)printf("%lld ",height[i]);printf("\n");
		for(int i=1;i<=n;i++)st[i][0]=height[i];
		for(int k=1;k<=19;k++){
			for(int i=1;i+(1<<k)-1<=n;i++)st[i][k]=min(st[i][k-1],st[i+(1<<(k-1))][k-1]);
		}
	}
	void SA(){
		int cnt=128,lcnt=0;
		for(int i=1;i<=cnt;i++)sum[i]=0;
	  for(int i=1;i<=n;i++)sum[rk[i]=s[i]]++;
		for(int i=1;i<=cnt;i++)sum[i]+=sum[i-1];
		for(int i=n;i>=1;i--)sa[sum[rk[i]]--]=i;
		for(int k=1;k<=n;k*=2){
			lcnt=cnt,cnt=0;
			for(int i=n;i>n-k;i--)id[++cnt]=i;
			for(int i=1;i<=n;i++)if(sa[i]>k)id[++cnt]=sa[i]-k;
			for(int i=0;i<=lcnt;i++)sum[i]=0;
			for(int i=1;i<=n;i++)sum[lrk[i]=rk[i]]++;
			for(int i=1;i<=lcnt;i++)sum[i]+=sum[i-1];
			for(int i=n;i>=1;i--)sa[sum[rk[id[i]]]--]=id[i];
			cnt=0;
			for(int i=1;i<=n;i++)if(cmp(sa[i],sa[i-1],k))rk[sa[i]]=rk[sa[i-1]];else rk[sa[i]]=++cnt;
			if(cnt==n)break;
		}
		build_height();
	}
}S;

int n,m,a[N],b[N],c[2*N],l1,l2;
char s[N];

signed main(void){
//	freopen("sa.in","r",stdin);
//	freopen("sa.out","w",stdout);
	n=read(),m=read(),scanf("%s",s+1);
	for(int i=1;i<=n;i++)S.s[i]=s[i];
	S.n=n,S.SA();
	while(m--){
		l1=read(),l2=read();
		for(int i=1;i<=l1;i++)a[i]=read(),c[i]=a[i];
		for(int i=1;i<=l2;i++)b[i]=read(),c[l1+i]=b[i];
		printf("%lld\n",S.get_ans(c,l1+l2)-S.get_ans(a,l1)-S.get_ans(b,l2));
	}
	return 0;
}
//start coding at 15:52 
//finish coding at 16:47
//finish dubging at 16:47